package demo1;

import java.util.Arrays;

public class Heap {
    //建堆(大根堆)(向下调整建堆)
    public void createHeap(int[] array) {
        //array.length - 1 是数组有效数字的最后一个下标
        //(arrat.length - 1 - 1) / 2  这个公式得到的就是父亲下标
        for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
            shiftDown(array,parent,array.length - 1);
        }
    }
    //向下调整
    public void shiftDown(int[] array, int parent, int end) {
        //得到父亲节点的左孩子的位置
        int child = parent * 2 + 1;
        //判断孩子下标有没有越界
        while (child <= end) {
            //判断有没有右孩子 并且  右孩子的值有没有左孩子大
            if (child + 1 <= end && array[child + 1] > array[child]) {
                child++;
            }
            //如果父亲下标的值小于孩子下标的值就进行交换   否则就退出循环
            //并且让parent = child 进入下一轮循环
            if (array[parent] < array[child]) {
                swap(array,parent,child);
                parent = child;
                child = parent * 2 + 1;
            } else {
                break;
            }
        }

    }
    //使用向上调整建堆
    public void createHeap1(int[] array) {
        for (int child = 1; child < array.length; child++) {
            shiftUp(array,child);
        }
    }
    //堆的插入
    public void insertNum(int[] array, int num) {
        int length = array.length;
        //array = Arrays.copyOf(array,array.length * 2);
        //在这里假设数组没满 就把Num放到length位置
        array[length] = num;
        shiftUp(array,length);
    }
    //堆的删除
    public void poll(int[] array) {
        //这里要注意  假设array.length - 1就是数组的有效数字的最后一个
        swap(array,0,array.length - 1);
        shiftDown(array,0,array.length - 2);
    }
    //向上调整
    public void shiftUp(int[] array, int child) {
        int parent = (child - 1) / 2;
        while (child > 0) {
            if (array[child] > array[parent]) {
                swap(array,child,parent);
                child = parent;
                parent = (child - 1) / 2;
            } else {
                break;
            }
        }
    }
    //交换
    public void swap(int[] array, int x, int y) {
        int temp = array[x];
        array[x] = array[y];
        array[y] = temp;
    }
}
